package day_2022_7_to_8.day48;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author haomin
 * @date 2022/07/26 10:27
 **/
public class Day11_2_Num137_SingleNumber {
    // 方法一：排序+遍历 当(nums[i] ！= nums[i-1] && nums[i] ！= nums[i+1])时，该值就是单身数
    class Solution {
        public int singleNumber(int[] nums) {
            int len = nums.length;
            if(len == 1) return nums[0];
            Arrays.sort(nums);
            // 第一个数就是单身数
            if(nums[0] != nums[1]) return nums[0];
            for(int i = 2;i < len-1;i++){
                if(!(nums[i] == nums[i-1] || nums[i] == nums[i+1])){
                    return nums[i];
                }
            }
            // 最后一个数是单身数
            return nums[len-1];
        }
    }

    // 方法二：方法一的改进
    class Solution2 {
        public int singleNumber(int[] nums) {
            if(nums.length == 1) return nums[0];
            Arrays.sort(nums);
            // 排序后3个3个相连，若出现一个于后两个不同，那一定是单身数
            for(int i = 0;i < nums.length-2;i+=3){
                if(nums[i] != nums[i+2]){
                    return nums[i];
                }
            }
            // 最后一个数是单身数
            return nums[nums.length-1];
        }
    }

    // 方法三：Map
    class Solution3 {
        public int singleNumber(int[] nums) {
            Map<Integer,Integer> map = new HashMap<>();
            // 将所有元素存入map
            for(int i : nums){
                if(map.containsKey(i)) {
                    map.replace(i,map.get(i)+1);
                }else {
                    map.put(i,1);
                }
            }
            // 若出现value 为1，那其一定是单身数
            for(int i : nums){
                if(map.get(i) == 1) return i;
            }
            return 0;
        }
    }
}